from enum import Enum
import copy
import pygame
import math
import numpy as np


class GameSetting(object):
    def __init__(self):
        self.window_size = (900, 600)
        self.background_color = (255, 255, 255)
        self.light_color = (124, 147, 165)
        self.dark_color = (87, 101, 112)
        self.line_width = 0  # edge line of each square's width
        self.frame_width = 3
        self.board_width = 0
        self.BLACK = (0, 0, 0)
        self.FRAME = (255, 223, 56)  # rectangle frame color
        self.axis_font = pygame.font.Font(None, self.axis_font_size())
        self.piece_imag_path = 'pieces_imag/'
        self.piece_style = 'style1'
        self.piece_images = []

    def axis_font_size(self):
        return int(self.square_length() / 3)

    def board_length(self):
        return int(min(self.window_size) * 0.8)

    def square_length(self):
        return int(self.board_length() / 8)

    def piece_length(self):
        return int(self.square_length() * 1.0)

    def board_location(self):
        return [int(self.window_size[0] / 2 - 4 * self.square_length()),
                int(self.window_size[1] / 2 - 4 * self.square_length())]

    def square_location(self, square_id):
        return [int(self.board_location()[0] + square_id[1] * self.square_length()),
                int(self.board_location()[1] + (7 - square_id[0]) * self.square_length())]

    def frame_location(self, square_id):
        squ_loc = self.square_location(square_id)
        return [int(squ_loc[0] + self.frame_width / 2), int(squ_loc[1] + self.frame_width / 2)]

    def draw_square(self, surface, square_id, square, selected=False):
        if (square_id[0] + square_id[1]) % 2 == 0:
            color = self.light_color
        else:
            color = self.dark_color
        pygame.draw.rect(surface, color,
                         self.square_location(square_id) + [self.square_length(), self.square_length()], 0)
        if self.line_width > 0:
            pygame.draw.rect(surface, self.BLACK, self.square_location(square_id) +
                             [self.square_length(), self.square_length()], self.line_width)
        # draw piece in that square
        if square.piece != Piece.empty and square.piece_color != Color.none:
            surface.blit(self.get_piece_imag(square.piece, square.piece_color), self.square_location(square_id))
        # if selected, draw rectangle frame
        if selected:
            pygame.draw.rect(surface, self.FRAME, self.frame_location(square_id) +
                             [self.square_length() - self.frame_width, self.square_length() - self.frame_width],
                             self.frame_width)
        pygame.display.update()

    def select_square(self, surface, square_id, square):
        self.draw_square(surface, square_id, square, selected=True)

    def unselect_square(self, surface, square_id, square):
        self.draw_square(surface, square_id, square, selected=False)

    def draw_board(self, surface, board):
        for i in range(8):
            for j in range(8):
                self.draw_square(surface, [i, j], board[i][j])
        if self.board_width > 0:
            pygame.draw.rect(surface, self.BLACK, self.board_location() +
                             [self.board_length(), self.board_length(), ], self.board_width)

        text_a = self.axis_font.render("a", True, self.dark_color)
        text_b = self.axis_font.render("b", True, self.light_color)
        text_c = self.axis_font.render("c", True, self.dark_color)
        text_d = self.axis_font.render("d", True, self.light_color)
        text_e = self.axis_font.render("e", True, self.dark_color)
        text_f = self.axis_font.render("f", True, self.light_color)
        text_g = self.axis_font.render("g", True, self.dark_color)
        text_h = self.axis_font.render("h", True, self.light_color)
        text_letter = [text_a, text_b, text_c, text_d, text_e, text_f, text_g, text_h]

        for j in range(8):
            surface.blit(text_letter[j], self.square_location([-1, j]))

        text_1 = self.axis_font.render("1", True, self.dark_color)
        text_2 = self.axis_font.render("2", True, self.light_color)
        text_3 = self.axis_font.render("3", True, self.dark_color)
        text_4 = self.axis_font.render("4", True, self.light_color)
        text_5 = self.axis_font.render("5", True, self.dark_color)
        text_6 = self.axis_font.render("6", True, self.light_color)
        text_7 = self.axis_font.render("7", True, self.dark_color)
        text_8 = self.axis_font.render("8", True, self.light_color)
        text_num = [text_1, text_2, text_3, text_4, text_5, text_6, text_7, text_8]
        for i in range(8):
            surface.blit(text_num[i], [self.square_location([i - 1, 0])[0] - self.axis_font_size() / 2,
                                       self.square_location([i - 1, 0])[1] - self.axis_font_size()])

    def load_piece_imag(self):
        # load piece images
        white_pawn = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_pawn.png').convert_alpha()
        white_knight = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_knight.png').convert_alpha()
        white_bishop = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_bishop.png').convert_alpha()
        white_rook = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_rook.png').convert_alpha()
        white_queen = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_queen.png').convert_alpha()
        white_king = pygame.image.load(self.piece_imag_path + self.piece_style + '/white_king.png').convert_alpha()

        black_pawn = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_pawn.png').convert_alpha()
        black_knight = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_knight.png').convert_alpha()
        black_bishop = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_bishop.png').convert_alpha()
        black_rook = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_rook.png').convert_alpha()
        black_queen = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_queen.png').convert_alpha()
        black_king = pygame.image.load(self.piece_imag_path + self.piece_style + '/black_king.png').convert_alpha()
        # adjust piece image scale
        white_pawn = pygame.transform.scale(white_pawn, (self.piece_length(), self.piece_length()))
        white_knight = pygame.transform.scale(white_knight, (self.piece_length(), self.piece_length()))
        white_bishop = pygame.transform.scale(white_bishop, (self.piece_length(), self.piece_length()))
        white_rook = pygame.transform.scale(white_rook, (self.piece_length(), self.piece_length()))
        white_queen = pygame.transform.scale(white_queen, (self.piece_length(), self.piece_length()))
        white_king = pygame.transform.scale(white_king, (self.piece_length(), self.piece_length()))

        black_pawn = pygame.transform.scale(black_pawn, (self.piece_length(), self.piece_length()))
        black_knight = pygame.transform.scale(black_knight, (self.piece_length(), self.piece_length()))
        black_bishop = pygame.transform.scale(black_bishop, (self.piece_length(), self.piece_length()))
        black_rook = pygame.transform.scale(black_rook, (self.piece_length(), self.piece_length()))
        black_queen = pygame.transform.scale(black_queen, (self.piece_length(), self.piece_length()))
        black_king = pygame.transform.scale(black_king, (self.piece_length(), self.piece_length()))

        return [white_pawn, white_knight, white_bishop, white_rook, white_queen, white_king,
                black_pawn, black_knight, black_bishop, black_rook, black_queen, black_king]

    def get_piece_imag(self, piece, color):
        if piece == Piece.empty:
            return None
        if color == Color.white:
            offset = -1
        else:
            offset = 5
        return self.piece_images[offset + piece.value]


class Piece(Enum):
    empty = 0
    pawn = 1
    knight = 2
    bishop = 3
    rook = 4
    queen = 5
    king = 6


class Color(Enum):
    none = 0
    white = 1
    black = -1


class Square(object):
    def __init__(self):
        self.piece = Piece.empty
        self.piece_color = Color.none

    def clear(self):
        self.piece = Piece.empty
        self.piece_color = Color.none

    def set(self, piece, color):
        self.piece = piece
        self.piece_color = color


class SpecialMovePermissionList(object):
    def __init__(self):
        self.white0_0 = True
        self.black0_0 = True
        self.white0_0_0 = True
        self.black0_0_0 = True
        self.white_passerby_square = []  # e.g: [d5, e6] means white can move d5xe6 (passerby)
        self.black_passerby_square = []


class Game(object):
    def __init__(self):
        self.board = [[Square() for _ in range(8)] for _ in range(8)]

        self.board[0][0].piece = Piece.rook
        self.board[0][1].piece = Piece.knight
        self.board[0][2].piece = Piece.bishop
        self.board[0][3].piece = Piece.queen
        self.board[0][4].piece = Piece.king
        self.board[0][5].piece = Piece.bishop
        self.board[0][6].piece = Piece.knight
        self.board[0][7].piece = Piece.rook
        for i in range(8):
            self.board[1][i].piece = Piece.pawn
            self.board[0][i].piece_color = Color.white
            self.board[1][i].piece_color = Color.white

        self.board[7][0].piece = Piece.rook
        self.board[7][1].piece = Piece.knight
        self.board[7][2].piece = Piece.bishop
        self.board[7][3].piece = Piece.queen
        self.board[7][4].piece = Piece.king
        self.board[7][5].piece = Piece.bishop
        self.board[7][6].piece = Piece.knight
        self.board[7][7].piece = Piece.rook
        for i in range(8):
            self.board[6][i].piece = Piece.pawn
            self.board[7][i].piece_color = Color.black
            self.board[6][i].piece_color = Color.black

        self.current_player = Color.white
        self.SpecialMovePermissionList = SpecialMovePermissionList()
        self.mouse_square_id = [-1, -1]
        self.selected_square_id = [-1, -1]
        self.selected_piece = Piece.empty
        self.selected_piece_color = Color.none
        self.white_player = 1   # 1: human, 0: computer
        self.black_player = 1

    def start(self):
        # initial setting
        self.white_player = int(input('select white player: 1=human, 0=computer\n'))
        while self.white_player != 1 and self.white_player != 0:
            self.white_player = int(input('invalid number, 1=human, 0=computer\n'))
        self.black_player = int(input('select black player: 1=human, 0=computer\n'))
        while self.black_player != 1 and self.black_player != 0:
            self.black_player = int(input('invalid number, 1=human, 0=computer\n'))

        pygame.init()
        game_setting = GameSetting()
        screen = pygame.display.set_mode(game_setting.window_size)
        pygame.display.set_caption('Chess Game')
        screen.fill(game_setting.background_color)
        pygame.display.flip()
        game_setting.piece_images = game_setting.load_piece_imag()
        game_setting.draw_board(screen, self.board)
        # play
        while True:
            # self.print()
            legal_moves = self.find_legal_moves(self.current_player)
            if not legal_moves:
                if self.is_check(self.current_player):
                    if self.current_player == Color.white:
                        print("black wins")
                    else:
                        print("white wins")
                else:
                    print("draw")
                exit(0)
            else:
                if (self.current_player == Color.white and self.white_player == 0) or \
                        (self.current_player == Color.black and self.black_player == 0):
                    # computer
                    # calculate best move
                    # src_square, dst_square, piece, promote_piece = self.computer_calculate_best_move(legal_moves)
                    next_move = self.minmaxsearch(legal_moves)
                    if len(next_move) == 3:
                        promote_piece = Piece.empty
                        src_square, dst_square, piece = self.minmaxsearch(legal_moves)
                    else:
                        src_square, dst_square, piece, promote_piece = self.minmaxsearch(legal_moves)
                    self.move(src_square, dst_square, piece, promote_piece)
                    game_setting.draw_board(screen, self.board)
                else:
                    # UI
                    # 为了防止游戏窗口启动会立马关闭，在其中增加一个游戏循环(无限循环)，
                    for event in pygame.event.get():
                        if event.type == pygame.QUIT:  # QUIT用户请求程序关闭
                            exit()
                        elif event.type == pygame.MOUSEMOTION:
                            x, y = pygame.mouse.get_pos()
                            # get the square id mouse is pointing at
                            self.mouse_square_id[1] = math.floor((x - game_setting.window_size[0] / 2)
                                                                 / game_setting.square_length()) + 4
                            self.mouse_square_id[0] = 3 - math.floor((y - game_setting.window_size[1] / 2)
                                                                     / game_setting.square_length())
                            continue
                        elif event.type == pygame.MOUSEBUTTONDOWN:
                            if event.button == 1:  # 1: left_click,2:middle_click,3:right_click,4:roll up,5:roll down
                                # left click outside the board, unselect the selected square
                                if self.mouse_square_id[0] < 0 or self.mouse_square_id[0] > 7 \
                                        or self.mouse_square_id[1] < 0 or self.mouse_square_id[1] > 7:
                                    if self.selected_square_id != [-1, -1]:
                                        game_setting.unselect_square(screen, self.selected_square_id,
                                                                     self.board[self.selected_square_id[0]]
                                                                     [self.selected_square_id[1]])
                                        self.selected_square_id = [-1, -1]
                                        self.selected_piece = Piece.empty
                                        self.selected_piece_color = Color.none
                                        game_setting.unselect_square(screen, self.selected_square_id,
                                                                     self.board[self.selected_square_id[0]]
                                                                     [self.selected_square_id[1]])
                                # left click inside the board, select the square
                                else:
                                    if self.selected_square_id != [-1, -1]:
                                        game_setting.unselect_square(screen, self.selected_square_id,
                                                                     self.board[self.selected_square_id[0]]
                                                                     [self.selected_square_id[1]])

                                    if self.selected_piece_color == self.current_player:
                                        # and then clicked on a non-friendly square, then try to move
                                        if self.board[self.mouse_square_id[0]][self.mouse_square_id[1]].piece_color != \
                                                self.current_player:
                                            if self.move(self.selected_square_id, self.mouse_square_id,
                                                         self.selected_piece)[0] <= 0:    # move unsuccessful
                                                self.selected_square_id = [-1, -1]
                                                self.selected_piece = Piece.empty
                                                self.selected_piece_color = Color.none
                                                game_setting.unselect_square(screen, self.selected_square_id,
                                                                             self.board[self.selected_square_id[0]]
                                                                             [self.selected_square_id[1]])
                                            else:
                                                game_setting.draw_board(screen, self.board)
                                        # selected another friendly piece, then switch selected_piece to it
                                        else:
                                            self.selected_square_id = copy.copy(self.mouse_square_id)
                                            self.selected_piece = \
                                                self.board[self.selected_square_id[0]][self.selected_square_id[1]].piece
                                            self.selected_piece_color = \
                                                self.board[self.selected_square_id[0]][
                                                    self.selected_square_id[1]].piece_color
                                            game_setting.select_square(screen, self.selected_square_id,
                                                                       self.board[self.selected_square_id[0]][
                                                                           self.selected_square_id[1]])
                                    # selected a non-friendly square
                                    else:
                                        self.selected_square_id = copy.copy(self.mouse_square_id)
                                        self.selected_piece = \
                                            self.board[self.selected_square_id[0]][self.selected_square_id[1]].piece
                                        self.selected_piece_color = \
                                            self.board[self.selected_square_id[0]][
                                                self.selected_square_id[1]].piece_color
                                        game_setting.select_square(screen, self.selected_square_id,
                                                                   self.board[self.selected_square_id[0]][
                                                                       self.selected_square_id[1]])

                                    game_setting.select_square(screen, self.mouse_square_id,
                                                               self.board[self.mouse_square_id[0]][
                                                                   self.mouse_square_id[1]])
                                    self.selected_square_id = copy.copy(self.mouse_square_id)
                                    self.selected_piece = \
                                        self.board[self.selected_square_id[0]][self.selected_square_id[1]].piece
                                    self.selected_piece_color = \
                                        self.board[self.selected_square_id[0]][self.selected_square_id[1]].piece_color
                            elif event.button == 3:
                                game_setting.unselect_square(screen, self.selected_square_id,
                                                             self.board[self.selected_square_id[0]]
                                                             [self.selected_square_id[1]])
                                self.selected_square_id = [-1, -1]
                                self.selected_piece = Piece.empty
                                self.selected_piece_color = Color.none
                            else:
                                continue
                        else:
                            continue

    def clear(self):
        for i in range(8):
            for j in range(8):
                self.board[i][j].clear()

    def set(self, dst_square, piece, color):
        self.board[dst_square[0]][dst_square[1]].piece = piece
        self.board[dst_square[0]][dst_square[1]].piece_color = color

    def check_legal_move(self, src_square_id, dst_square_id):  # check if move violates the rules
        # check square id overflow
        if 0 <= src_square_id[0] <= 7 and 0 <= src_square_id[1] <= 7 \
                and 0 <= dst_square_id[0] <= 7 and 0 <= dst_square_id[1] <= 7:
            pass
        else:
            return False
        test_board = copy.deepcopy(self.board)
        player = test_board[src_square_id[0]][src_square_id[1]].piece_color
        piece = test_board[src_square_id[0]][src_square_id[1]].piece
        dst_color = test_board[dst_square_id[0]][dst_square_id[1]].piece_color
        # check empty source square
        if player == Color.none:
            return False
        # check friendly capture
        if player == dst_color:
            return False
        # check same-square move
        if src_square_id == dst_square_id:
            return False

        # 1.check moving rule violence
        if piece == Piece.pawn:
            # just move
            # move 1 square
            if src_square_id[1] == dst_square_id[1] and dst_square_id[0] == src_square_id[0] + player.value \
                    and dst_color == Color.none:
                pass
            # first time, move 2 square -- white
            elif src_square_id[1] == dst_square_id[1] and src_square_id[0] == 1 and dst_square_id[0] == 3 \
                    and player == Color.white and dst_color == Color.none:
                pass
            # first time, move 2 square -- black
            elif src_square_id[1] == dst_square_id[1] and src_square_id[0] == 6 and dst_square_id[0] == 4 \
                    and player == Color.black and dst_color == Color.none:
                pass
            # capture enemy pieces
            elif abs(src_square_id[1] - dst_square_id[1]) == 1 and dst_square_id[0] == src_square_id[0] + player.value \
                    and dst_color != Color.none and dst_color != player:
                pass
            # passer-by captures judgement should be added here
            elif [src_square_id, dst_square_id] in self.SpecialMovePermissionList.white_passerby_square or \
                    [src_square_id, dst_square_id] in self.SpecialMovePermissionList.black_passerby_square:
                pass
            else:
                return False

        elif piece == Piece.knight:
            if ((abs(dst_square_id[0] - src_square_id[0]) == 2 and abs(dst_square_id[1] - src_square_id[1]) == 1)
                or (abs(dst_square_id[0] - src_square_id[0]) == 1 and abs(dst_square_id[1] - src_square_id[1]) == 2)) \
                    and dst_color != player:
                pass
            else:
                return False

        elif piece == Piece.bishop:
            # check dialog satisfaction
            if abs(dst_square_id[0] - src_square_id[0]) != abs(dst_square_id[1] - src_square_id[1]):
                return False
            # check block of other pieces
            dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))  # direction
            dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))  # of checking
            temp_i = src_square_id[0] + dir_i
            temp_j = src_square_id[1] + dir_j
            while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
                if test_board[temp_i][temp_j].piece == Piece.empty:
                    temp_i = temp_i + dir_i
                    temp_j = temp_j + dir_j
                    continue
                else:
                    return False  # blocked by other pieces.

        elif piece == Piece.rook:
            # check line satisfaction
            if src_square_id[0] != dst_square_id[0] and src_square_id[1] != dst_square_id[1]:
                return False
            # check block of other pieces
            if src_square_id[0] == dst_square_id[0]:
                dir_i = 0
            else:
                dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))
            if src_square_id[1] == dst_square_id[1]:
                dir_j = 0
            else:
                dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))
            temp_i = src_square_id[0] + dir_i
            temp_j = src_square_id[1] + dir_j
            while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
                if test_board[temp_i][temp_j].piece == Piece.empty:
                    temp_i = temp_i + dir_i
                    temp_j = temp_j + dir_j
                    continue
                else:
                    return False  # blocked by other pieces.

        elif piece == Piece.queen:
            # check dialog or line satisfaction
            if (abs(dst_square_id[0] - src_square_id[0]) != abs(dst_square_id[1] - src_square_id[1])) \
                    and (src_square_id[0] != dst_square_id[0] and src_square_id[1] != dst_square_id[1]):
                return False
            # check block of other pieces
            if src_square_id[0] == dst_square_id[0]:
                dir_i = 0
            else:
                dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))
            if src_square_id[1] == dst_square_id[1]:
                dir_j = 0
            else:
                dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))
            temp_i = src_square_id[0] + dir_i
            temp_j = src_square_id[1] + dir_j
            while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
                if test_board[temp_i][temp_j].piece == Piece.empty:
                    temp_i = temp_i + dir_i
                    temp_j = temp_j + dir_j
                    continue
                else:
                    return False  # blocked by other pieces.
        elif piece == Piece.king:
            # castling check
            if player == Color.white:
                # white attempts to 0-0
                if src_square_id == [0, 4] and dst_square_id == [0, 6] and self.SpecialMovePermissionList.white0_0:
                    # castling is blocked by other pieces
                    if test_board[0][5].piece != piece.empty or test_board[0][6].piece != piece.empty:
                        return False
                    # put extra kings on the board to test if king is being attacked before/while in/after castling.
                    test_board[0][5].piece = Piece.king
                    test_board[0][6].piece = Piece.king
                    test_board[0][5].piece_color = Color.white
                    test_board[0][6].piece_color = Color.white
                    count, attackers = is_check(test_board, player)
                    if count != 0:
                        return False
                    # not being checked, nor banned by SpecialMovePermissionList
                    return True
                # white attempts to 0-0-0
                elif src_square_id == [0, 4] and dst_square_id == [0, 2] and self.SpecialMovePermissionList.white0_0_0:
                    # castling is blocked by other pieces
                    if test_board[0][3].piece != piece.empty or test_board[0][2].piece != piece.empty:
                        return False
                    # put extra kings on the board to test if king is being attacked before/while in/after castling.
                    test_board[0][3].piece = Piece.king
                    test_board[0][2].piece = Piece.king
                    test_board[0][3].piece_color = Color.white
                    test_board[0][2].piece_color = Color.white
                    count, attackers = is_check(test_board, player)
                    if count != 0:
                        return False
                    # not being checked, nor banned by SpecialMovePermissionList
                    return True
            elif player == Color.black:
                # black attempts to 0-0
                if src_square_id == [7, 4] and dst_square_id == [7, 6] and self.SpecialMovePermissionList.black0_0:
                    # castling is blocked by other pieces
                    if test_board[7][5].piece != piece.empty or test_board[7][6].piece != piece.empty:
                        return False
                    # put extra kings on the board to test if king is being attacked before/while in/after castling.
                    test_board[7][5].piece = Piece.king
                    test_board[7][6].piece = Piece.king
                    test_board[7][5].piece_color = Color.black
                    test_board[7][6].piece_color = Color.black
                    count, attackers = is_check(test_board, player)
                    if count != 0:
                        return False
                    # not being checked, nor banned by SpecialMovePermissionList
                    return True
                elif src_square_id == [7, 4] and dst_square_id == [7, 2] and self.SpecialMovePermissionList.black0_0_0:
                    # castling is blocked by other pieces
                    if test_board[7][3].piece != piece.empty or test_board[7][2].piece != piece.empty:
                        return False
                    # put extra kings on the board to test if king is being attacked before/while in/after castling.
                    test_board[7][3].piece = Piece.king
                    test_board[7][2].piece = Piece.king
                    test_board[7][3].piece_color = Color.black
                    test_board[7][2].piece_color = Color.black
                    count, attackers = is_check(test_board, player)
                    if count != 0:
                        return False
                    # not being checked, nor banned by SpecialMovePermissionList
                    return True

            # check distance satisfaction
            if abs(dst_square_id[0] - src_square_id[0]) > 1 or abs(dst_square_id[1] - src_square_id[1]) > 1:
                return False

        # 2. check king-being-attacked violence
        test_board[dst_square_id[0]][dst_square_id[1]].piece = \
            test_board[src_square_id[0]][src_square_id[1]].piece
        test_board[dst_square_id[0]][dst_square_id[1]].piece_color = \
            test_board[src_square_id[0]][src_square_id[1]].piece_color
        test_board[src_square_id[0]][src_square_id[1]].piece = Piece.empty
        test_board[src_square_id[0]][src_square_id[1]].piece_color = Color.none
        count, attackers = is_check(test_board, player)
        if count != 0:
            return False

        # after all rule violence check
        return True

    def move(self, src_square_id, dst_square_id, src_piece, promote_piece=Piece.empty):
        promote_flag = 0  # if this move is a promote, this flag is 1
        piece_color = self.board[src_square_id[0]][src_square_id[1]].piece_color
        piece = self.board[src_square_id[0]][src_square_id[1]].piece
        if self.board[src_square_id[0]][src_square_id[1]].piece == Piece.empty:
            return 0, 0  # invalid move for empty source square
        if not self.check_legal_move(src_square_id, dst_square_id):
            return -1, 0  # invalid move for rule violence
        if self.board[dst_square_id[0]][dst_square_id[1]].piece != Piece.empty:
            capture_flag = 2  # capture
        else:
            capture_flag = 1  # no capture
        if (dst_square_id[0] == 7 or dst_square_id[0] == 0) \
                and self.board[src_square_id[0]][src_square_id[1]].piece == Piece.pawn:
            promote_flag = 1
            if promote_piece == Piece.empty:  # unspecified promote piece
                self.board[dst_square_id[0]][dst_square_id[1]].piece = self.get_promote_piece(dst_square_id)
            else:  # specified promote piece
                self.board[dst_square_id[0]][dst_square_id[1]].piece = promote_piece
        # move piece from src square to dst square
        else:
            self.board[dst_square_id[0]][dst_square_id[1]].piece = self.board[src_square_id[0]][src_square_id[1]].piece
        self.board[dst_square_id[0]][dst_square_id[1]].piece_color = \
            self.board[src_square_id[0]][src_square_id[1]].piece_color
        self.board[src_square_id[0]][src_square_id[1]].clear()

        # if castling, move rook by king's the other side
        # white 0-0
        if src_square_id == [0, 4] and dst_square_id == [0, 6] and src_piece == Piece.king:
            self.board[0][7].clear()
            self.board[0][5].piece = Piece.rook
            self.board[0][5].piece_color = Color.white
        # white 0-0-0
        elif src_square_id == [0, 4] and dst_square_id == [0, 2] and src_piece == Piece.king:
            self.board[0][0].clear()
            self.board[0][3].piece = Piece.rook
            self.board[0][3].piece_color = Color.white
        # black 0-0
        elif src_square_id == [7, 4] and dst_square_id == [7, 6] and src_piece == Piece.king:
            self.board[7][7].clear()
            self.board[7][5].piece = Piece.rook
            self.board[7][5].piece_color = Color.black
        # black 0-0-0
        elif src_square_id == [7, 4] and dst_square_id == [7, 2] and src_piece == Piece.king:
            self.board[7][0].clear()
            self.board[7][3].piece = Piece.rook
            self.board[7][3].piece_color = Color.black

        # update SpecialMovePermissionList
        # check passer-by:
        if piece_color == Color.white:
            # if taking passer-by, clear opposite pawn square
            if [src_square_id, dst_square_id] in self.SpecialMovePermissionList.white_passerby_square:
                self.board[dst_square_id[0] - 1][dst_square_id[1]].piece = Piece.empty
                self.board[dst_square_id[0] - 1][dst_square_id[1]].piece_color = Color.none
            # clear opposite passerby square
            self.SpecialMovePermissionList.white_passerby_square.clear()
            if piece == Piece.pawn and src_square_id[0] == 1 and dst_square_id[0] == 3:
                # check left side
                if src_square_id[1] != 0:
                    if self.board[3][src_square_id[1] - 1].piece == Piece.pawn and \
                            self.board[3][src_square_id[1] - 1].piece_color == Color.black:
                        self.SpecialMovePermissionList.black_passerby_square.append([[3, src_square_id[1] - 1],
                                                                                     [2, src_square_id]])
                # check right side
                if src_square_id[1] != 7:
                    if self.board[3][src_square_id[1] + 1].piece == Piece.pawn and \
                            self.board[3][src_square_id[1] + 1].piece_color == Color.black:
                        self.SpecialMovePermissionList.black_passerby_square.append([[3, src_square_id[1] + 1],
                                                                                     [2, src_square_id]])
        if piece_color == Color.black:
            # if taking passer-by, clear opposite pawn square
            if [src_square_id, dst_square_id] in self.SpecialMovePermissionList.black_passerby_square:
                self.board[dst_square_id[0] + 1][dst_square_id[1]].piece = Piece.empty
                self.board[dst_square_id[0] + 1][dst_square_id[1]].piece_color = Color.none
            # clear opposite passerby square
            self.SpecialMovePermissionList.black_passerby_square.clear()
            if piece == Piece.pawn and src_square_id[0] == 6 and dst_square_id[0] == 4:
                # check left side
                if src_square_id[1] != 0:
                    if self.board[4][src_square_id[1] - 1].piece == Piece.pawn and \
                            self.board[4][src_square_id[1] - 1].piece_color == Color.white:
                        self.SpecialMovePermissionList.white_passerby_square.append([[4, src_square_id[1] - 1],
                                                                                     [5, src_square_id[1]]])
                # check right side
                if src_square_id[1] != 7:
                    if self.board[4][src_square_id[1] + 1].piece == Piece.pawn and \
                            self.board[4][src_square_id[1] + 1].piece_color == Color.white:
                        self.SpecialMovePermissionList.white_passerby_square.append([[4, src_square_id[1] + 1],
                                                                                     [5, src_square_id[1]]])

        # check castle:
        # firstly, check if rook and king is still in their original square
        # check white 0-0:
        if self.SpecialMovePermissionList.white0_0:
            # piece in square h1 is not white rook: deny white 0-0
            if self.board[0][7].piece != Piece.rook or self.board[0][7].piece_color != Color.white:
                self.SpecialMovePermissionList.white0_0 = False
            # piece in square e1 is not white king: deny white castling
            if self.board[0][4].piece != Piece.king or self.board[0][4].piece_color != Color.white:
                self.SpecialMovePermissionList.white0_0_0 = False
                self.SpecialMovePermissionList.white0_0 = False
        # check white 0-0-0:
        if self.SpecialMovePermissionList.white0_0_0:
            # piece in square a1 is not white rook: deny white 0-0_0
            if self.board[0][0].piece != Piece.rook or self.board[0][0].piece_color != Color.white:
                self.SpecialMovePermissionList.white0_0_0 = False
            # piece in square e1 is not white king: deny white castling
            if self.board[0][4].piece != Piece.king or self.board[0][4].piece_color != Color.white:
                self.SpecialMovePermissionList.white0_0_0 = False
                self.SpecialMovePermissionList.white0_0 = False

        # check black 0-0:
        if self.SpecialMovePermissionList.black0_0:
            # piece in square h8 is not black rook: deny black 0-0
            if self.board[7][7].piece != Piece.rook or self.board[7][7].piece_color != Color.black:
                self.SpecialMovePermissionList.black0_0 = False
            # piece in square e8 is not black king: deny black castling
            if self.board[7][4].piece != Piece.king or self.board[7][4].piece_color != Color.black:
                self.SpecialMovePermissionList.black0_0_0 = False
                self.SpecialMovePermissionList.black0_0 = False

        # check black 0-0-0:
        if self.SpecialMovePermissionList.black0_0_0:
            # piece in square a8 is not black rook: deny black 0-0-0
            if self.board[7][0].piece != Piece.rook or self.board[7][0].piece_color != Color.black:
                self.SpecialMovePermissionList.black0_0_0 = False
            # piece in square e8 is not black king: deny black castling
            if self.board[7][4].piece != Piece.king or self.board[7][4].piece_color != Color.black:
                self.SpecialMovePermissionList.black0_0_0 = False
                self.SpecialMovePermissionList.black0_0 = False

        # secondly, check the current move ( e.g: after king moves, deny both side castling)
        if piece == Piece.king:
            if piece_color == Color.white:
                self.SpecialMovePermissionList.white0_0 = False
                self.SpecialMovePermissionList.white0_0_0 = False
            elif piece_color == Color.black:
                self.SpecialMovePermissionList.black0_0 = False
                self.SpecialMovePermissionList.black0_0_0 = False

        elif piece == Piece.rook:
            if piece_color == Color.white:
                if src_square_id == [0, 0]:  # a1 rook moves, deny white 0-0-0
                    self.SpecialMovePermissionList.white0_0_0 = False
                elif src_square_id == [0, 7]:  # h1 rook moves, deny white 0-0
                    self.SpecialMovePermissionList.white0_0 = False
            elif piece_color == Color.black:
                if src_square_id == [7, 0]:  # a8 rook moves, deny black 0-0-0
                    self.SpecialMovePermissionList.black0_0_0 = False
                elif src_square_id == [7, 7]:  # h8 rook moves, deny black 0-0
                    self.SpecialMovePermissionList.black0_0 = False

        # switch player
        if self.current_player == Color.white:
            self.current_player = Color.black
        else:
            self.current_player = Color.white

        return capture_flag, promote_flag

    def is_check(self, player):  # define if player is being checked(将军)
        count = 0  # the number of enemy pieces that attacks the opposite king, may be 0,1 or 2 in valid states.
        attackers = []  # the location and piece_name of all attackers
        # search for the king
        for i in range(8):
            for j in range(8):
                if self.board[i][j].piece == Piece.king and self.board[i][j].piece_color == player:
                    # main part
                    # check straight line attackers (queen, rook & bishop)
                    for direction in range(8):
                        temp_i = i
                        temp_j = j
                        while 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            # for empty line, continue search
                            dir_x = [-1, 1, 0, 0, -1, 1, 1, -1]
                            dir_y = [0, 0, 1, -1, 1, 1, -1, -1]
                            if self.board[temp_i][temp_j].piece == Piece.empty or (temp_i == i and temp_j == j):

                                temp_i = temp_i + dir_x[direction]
                                temp_j = temp_j + dir_y[direction]
                                continue
                            # found an attacker piece: for dir=0~3,found rook or queen;for dir=4~7,found bishop or queen
                            elif self.board[temp_i][temp_j].piece_color != player \
                                    and (self.board[temp_i][temp_j].piece == Piece.queen
                                         or (0 <= direction <= 3 and self.board[temp_i][temp_j].piece == Piece.rook)
                                         or (4 <= direction <= 7 and self.board[temp_i][temp_j].piece == Piece.bishop)):
                                count = count + 1
                                attackers.append([[temp_i, temp_j], self.board[temp_i][temp_j].piece])
                                break
                            # found an non_attacker piece (or friendly piece)
                            else:
                                break
                    # check knight attackers
                    x_values = [1, 2, 2, 1, -1, -2, -2, -1]
                    y_values = [2, 1, -1, -2, -2, -1, 1, 2]
                    for direction in range(8):
                        temp_i = i + x_values[direction]
                        temp_j = j + y_values[direction]
                        if 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            if (self.board[temp_i][temp_j].piece == Piece.knight
                                    and self.board[temp_i][temp_j].piece_color != player):
                                count = count + 1
                                attackers.append([[temp_i, temp_j], self.board[temp_i][temp_j].piece])
                    # check pawn attackers
                    if player == Color.white:
                        temp_i = i + 1
                    else:
                        temp_i = i - 1
                    temp_j = j + 1  # check right
                    if 1 <= temp_i <= 6 and 0 <= temp_j <= 7 and self.board[temp_i][temp_j].piece == Piece.pawn \
                            and self.board[temp_i][temp_j].piece_color != player:
                        count = count + 1
                        attackers.append([[temp_i, temp_j], self.board[temp_i][temp_j].piece])
                    temp_j = j - 1  # check left
                    if 1 <= temp_i <= 6 and 0 <= temp_j <= 7 and self.board[temp_i][temp_j].piece == Piece.pawn \
                            and self.board[temp_i][temp_j].piece_color != player:
                        count = count + 1
                        attackers.append([[temp_i, temp_j], self.board[temp_i][temp_j].piece])

                    # check king attacker (used to judge illegal moves)
                    x_values = [1, 1, 0, -1, -1, -1, 0, 1]
                    y_values = [0, 1, 1, 1, 0, -1, -1, -1]
                    for direction in range(8):
                        temp_i = i + x_values[direction]
                        temp_j = j + y_values[direction]
                        if 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            if (self.board[temp_i][temp_j].piece == Piece.king
                                    and self.board[temp_i][temp_j].piece_color != player):
                                count = count + 1
                                attackers.append([[temp_i, temp_j], self.board[temp_i][temp_j].piece])
        return count, attackers

    def find_legal_moves(self, player):  # find all legal moves of that player
        legal_moves = []  # store all legal moves
        # count, attackers = self.is_check(player)
        # if count == 0:  # in current situation, player is not being checked. Any legal move is considered.
        for i in range(8):
            for j in range(8):
                if self.board[i][j].piece_color != player:
                    continue
                # found a friendly piece
                piece = self.board[i][j].piece
                piece_color = self.board[i][j].piece_color
                if piece == Piece.pawn:
                    if self.check_legal_move([i, j], [i + player.value, j]):
                        legal_moves.append([[i, j], [i + player.value, j], Piece.pawn])
                    if self.check_legal_move([i, j], [i + player.value, j + 1]):
                        legal_moves.append([[i, j], [i + player.value, j + 1], Piece.pawn])
                    if self.check_legal_move([i, j], [i + player.value, j - 1]):
                        legal_moves.append([[i, j], [i + player.value, j - 1], Piece.pawn])
                    if self.check_legal_move([i, j], [i + 2 * player.value, j]):
                        legal_moves.append([[i, j], [i + 2 * player.value, j], Piece.pawn])

                elif piece == Piece.knight:
                    if self.check_legal_move([i, j], [i + 1, j + 2]):
                        legal_moves.append([[i, j], [i + 1, j + 2], Piece.knight])
                    if self.check_legal_move([i, j], [i + 1, j - 2]):
                        legal_moves.append([[i, j], [i + 1, j - 2], Piece.knight])
                    if self.check_legal_move([i, j], [i - 1, j + 2]):
                        legal_moves.append([[i, j], [i - 1, j + 2], Piece.knight])
                    if self.check_legal_move([i, j], [i - 1, j - 2]):
                        legal_moves.append([[i, j], [i - 1, j - 2], Piece.knight])
                    if self.check_legal_move([i, j], [i + 2, j + 1]):
                        legal_moves.append([[i, j], [i + 2, j + 1], Piece.knight])
                    if self.check_legal_move([i, j], [i + 2, j - 1]):
                        legal_moves.append([[i, j], [i + 2, j - 1], Piece.knight])
                    if self.check_legal_move([i, j], [i - 2, j + 1]):
                        legal_moves.append([[i, j], [i - 2, j + 1], Piece.knight])
                    if self.check_legal_move([i, j], [i - 2, j - 1]):
                        legal_moves.append([[i, j], [i - 2, j - 1], Piece.knight])

                elif piece == Piece.bishop:
                    dir_x = [1, 1, -1, -1]
                    dir_y = [1, -1, 1, -1]
                    for direction in range(4):
                        temp_i = i + dir_x[direction]
                        temp_j = j + dir_y[direction]
                        while 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            if self.check_legal_move([i, j], [temp_i, temp_j]):
                                legal_moves.append([[i, j], [temp_i, temp_j], piece])
                                # if find an enemy piece, end this line's search
                                if self.board[temp_i][temp_j].piece_color.value == player.value * (-1):
                                    break
                                temp_i = temp_i + dir_x[direction]
                                temp_j = temp_j + dir_y[direction]
                            else:
                                if self.board[temp_i][temp_j].piece_color != Color.none:
                                    break  # if find a piece, end this line's search.
                                else:  # if not, but still illegal move, it's probably due to friendly king
                                    # is being checked.
                                    temp_i = temp_i + dir_x[direction]
                                    temp_j = temp_j + dir_y[direction]

                elif piece == Piece.rook:
                    dir_x = [1, 0, -1, 0]
                    dir_y = [0, 1, 0, -1]
                    for direction in range(4):
                        temp_i = i + dir_x[direction]
                        temp_j = j + dir_y[direction]
                        while 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            if self.check_legal_move([i, j], [temp_i, temp_j]):
                                legal_moves.append([[i, j], [temp_i, temp_j], piece])
                                # if find an enemy piece, end this line's search
                                if self.board[temp_i][temp_j].piece_color.value == player.value * (-1):
                                    break
                                temp_i = temp_i + dir_x[direction]
                                temp_j = temp_j + dir_y[direction]
                            else:
                                if self.board[temp_i][temp_j].piece_color != Color.none:
                                    break  # if find a friendly piece, end this line's search.
                                else:
                                    temp_i = temp_i + dir_x[direction]
                                    temp_j = temp_j + dir_y[direction]

                elif piece == Piece.queen:
                    dir_x = [1, 1, -1, -1, 1, 0, -1, 0]
                    dir_y = [1, -1, 1, -1, 0, 1, 0, -1]
                    for direction in range(8):
                        temp_i = i + dir_x[direction]
                        temp_j = j + dir_y[direction]
                        while 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                            if self.check_legal_move([i, j], [temp_i, temp_j]):
                                legal_moves.append([[i, j], [temp_i, temp_j], piece])
                                # if find an enemy piece, end this line's search
                                if self.board[temp_i][temp_j].piece_color.value == player.value * (-1):
                                    break
                                temp_i = temp_i + dir_x[direction]
                                temp_j = temp_j + dir_y[direction]
                            else:
                                if self.board[temp_i][temp_j].piece_color != Color.none:
                                    break  # if find a piece, end this line's search.
                                else:  # if not, but still illegal move, it's probably due to friendly king
                                    # is being checked.
                                    temp_i = temp_i + dir_x[direction]
                                    temp_j = temp_j + dir_y[direction]

                elif piece == Piece.king:
                    dir_x = [0, 1, 1, 1, 0, -1, -1, -1]
                    dir_y = [1, 1, 0, -1, -1, -1, 0, 1]
                    for direction in range(8):
                        temp_i = i + dir_x[direction]
                        temp_j = j + dir_y[direction]
                        if self.check_legal_move([i, j], [temp_i, temp_j]):
                            legal_moves.append([[i, j], [temp_i, temp_j], Piece.king])
                    if piece_color == Color.white:
                        if self.SpecialMovePermissionList.white0_0 and self.check_legal_move([0, 4], [0, 6]):
                            legal_moves.append([[0, 4], [0, 6], Piece.king])
                        if self.SpecialMovePermissionList.white0_0_0 and self.check_legal_move([0, 4], [0, 2]):
                            legal_moves.append([[0, 4], [0, 2], Piece.king])
                    elif piece_color == Color.black:
                        if self.SpecialMovePermissionList.black0_0 and self.check_legal_move([7, 4], [7, 6]):
                            legal_moves.append([[7, 4], [7, 6], Piece.king])
                        if self.SpecialMovePermissionList.black0_0_0 and self.check_legal_move([7, 4], [7, 2]):
                            legal_moves.append([[7, 4], [7, 2], Piece.king])
        return legal_moves

    def is_checkmate(self, player):  # define if player is checkmated and lose.
        pass

    def implement_move(self, move, legal_moves):  # implement move in writing style into square ids
        pawn_capture_shorts_flag = 0  # if move is short for pawn captures
        promotion_flag = 0
        promote_piece = Piece.empty
        piece = Piece.empty
        src_i = src_j = 0
        move = move.replace('x', '')  # delete all 'x' characters
        move = move.replace('+', '')  # delete all '+' characters
        move = move.replace('#', '')  # delete all '#' characters
        move = move.replace('=', '')  # delete all '=' characters

        if is_letter(move[0]) == 2:  # move start with capital letter, that is piece name.
            if len(move) <= 2:
                print("move too short")
                return []
            elif move[0] == 'K':
                piece = Piece.king
            elif move[0] == 'Q':
                piece = Piece.queen
            elif move[0] == 'R':
                piece = Piece.rook
            elif move[0] == 'N':
                piece = Piece.knight
            elif move[0] == 'B':
                piece = Piece.bishop
            elif move[0] == 'P':
                piece = Piece.pawn  # not recommended
            else:
                print("illegal piece name")
                return []
            move = move[1:]  # remove piece name after implementation

        elif is_letter(move[0]) == 1:  # move start with non-capital letter, then moving piece is pawn
            piece = Piece.pawn
            # handle promotion
            if is_letter(move[-1]) == 2:
                promotion_flag = 1
                if move[-1] == 'Q':
                    promote_piece = Piece.queen
                elif move[-1] == 'R':
                    promote_piece = Piece.rook
                elif move[-1] == 'N':
                    promote_piece = Piece.knight
                elif move[-1] == 'B':
                    promote_piece = Piece.bishop
                else:
                    print("illegal promote piece")
                    return []

                move = move[:-1]

        else:  # move start with non-letter character, suggesting castling
            if move == '0-0':
                if self.current_player == Color.white:
                    return [[0, 4], [0, 6], Piece.king]
                elif self.current_player == Color.black:
                    return [[7, 4], [7, 6], Piece.king]
            elif move == '0-0-0':
                if self.current_player == Color.white:
                    return [[0, 4], [0, 2], Piece.king]
                elif self.current_player == Color.black:
                    return [[7, 4], [7, 2], Piece.king]

        # the remaining part is src and dst square id
        # implement pawn captures
        if piece == Piece.pawn and is_letter(move[-1]):
            pawn_capture_shorts_flag = 1
            [src_i, src_j] = [-1, ord(move[0]) - ord('a')]
            dst_square_id = [-1, ord(move[1]) - ord('a')]
        else:
            dst_square_id = self.square_name(move[-2:])
        move = move[:-2]
        if pawn_capture_shorts_flag:
            pass
        elif len(move) == 2:  # 2 characters remaining, that is src_square name
            [src_i, src_j] = self.square_name(move)
        elif len(move) == 1:  # 1 character remaining, that is 1 coordinate of src_square name
            if is_letter(move[0]):
                src_j = ord(move[0]) - ord('a')
                src_i = -1
            elif is_num(move[0]):
                src_i = int(move[0]) - 1
                src_j = -1
            else:
                print("illegal square name")
                return []
        elif len(move) == 0:
            src_i = src_j = -1
        else:
            print("can't implement move")
            return []
        # find possible legal move
        possible_moves = []
        for legal_move in legal_moves:
            # skip those dst square id or piece doesn't match
            # used for pawn capture short-records.
            if dst_square_id[0] == -1 and dst_square_id[1] == legal_move[1][1] and legal_move[2] == piece == Piece.pawn:
                pass
            elif legal_move[1] != dst_square_id or legal_move[2] != piece:
                continue
            # skip those src square id doesn't match
            if src_i != -1 and src_i != legal_move[0][0]:
                continue
            if src_j != -1 and src_j != legal_move[0][1]:
                continue
            possible_moves.append(legal_move)
        if len(possible_moves) > 1:
            print("can't define the only move")
            return []
        elif len(possible_moves) == 0:
            print("illegal move")
            return []
        else:
            if promotion_flag:
                possible_moves[0].append(promote_piece)
            return possible_moves[0]

    # core function, calculate best move
    def computer_calculate_best_move(self, legal_moves):
        # in test, use console manually to input move
        promote_piece = Piece.empty
        # enter_move = input("please enter move:")
        enter_move = self.minmaxsearch(legal_moves)
        implementation_of_move = self.implement_move(enter_move, legal_moves)
        while not implementation_of_move:
            enter_move = input("please enter move again:")
            implementation_of_move = self.implement_move(enter_move, legal_moves)
        if len(implementation_of_move) == 3:
            promote_piece = Piece.empty
        elif len(implementation_of_move) == 4:
            promote_piece = implementation_of_move[3]
        else:
            print("wrong number of args")
            exit()
        return implementation_of_move[0], implementation_of_move[1], implementation_of_move[2], promote_piece

    def print(self):
        i = 7
        print("   =================================")
        while i >= 0:
            print(" ", end="")
            print(i + 1, end=" ")
            print("|", end=" ")
            for j in range(8):
                if self.board[i][j].piece == Piece.empty:
                    print(" ", end=" ")
                elif self.board[i][j].piece == Piece.pawn:
                    if self.board[i][j].piece_color == Color.white:
                        print("P", end=" ")
                    else:
                        print("p", end=" ")
                elif self.board[i][j].piece == Piece.knight:
                    if self.board[i][j].piece_color == Color.white:
                        print("N", end=" ")
                    else:
                        print("n", end=" ")
                elif self.board[i][j].piece == Piece.bishop:
                    if self.board[i][j].piece_color == Color.white:
                        print("B", end=" ")
                    else:
                        print("b", end=" ")
                elif self.board[i][j].piece == Piece.rook:
                    if self.board[i][j].piece_color == Color.white:
                        print("R", end=" ")
                    else:
                        print("r", end=" ")
                elif self.board[i][j].piece == Piece.queen:
                    if self.board[i][j].piece_color == Color.white:
                        print("Q", end=" ")
                    else:
                        print("q", end=" ")
                elif self.board[i][j].piece == Piece.king:
                    if self.board[i][j].piece_color == Color.white:
                        print("K", end=" ")
                    else:
                        print("k", end=" ")
                print("|", end=" ")
            i = i - 1
            print("")
            if i >= 0:
                print("   |---+---+---+---+---+---+---+---|")
            else:
                print("   =================================")
        print("     a   b   c   d   e   f   g   h")

    def get_promote_piece(self, dst_square_id):
        if (dst_square_id[0] == 7 and self.white_player == 0) or \
                (dst_square_id[0] == 1 and self.black_player == 0):  # computer
            return Piece.queen
        else:  # human
            print('enter promote piece in short\n')
            while True:
                promote_piece = input()
                if promote_piece == 'Q':
                    return Piece.queen
                elif promote_piece == 'R':
                    return Piece.rook
                elif promote_piece == 'N':
                    return Piece.knight
                elif promote_piece == 'B':
                    return Piece.bishop
                print('invalid piece, please enter again\n')

    def minmaxsearch(self, legal_moves):
        values = []
        values_temp = []
        depth = 2
        M = 100000000000000
        alpha = -M
        beta = M
        for moves in legal_moves:
            current_game = copy.deepcopy(self)
            if moves[2] == Piece.pawn:
                if moves[1][0] - moves[0][0] == 1:
                    if moves[1][0] == 7:
                        current_game.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        values.append(np.max(values_temp))
                        values_temp = []
                    else:
                        current_game.move(moves[0], moves[1], moves[2])
                        values.append(self.min_value(current_game, depth, alpha, beta))
                elif moves[1][0] - moves[0][0] == -1:
                    if moves[1][0] == 0:
                        current_game.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        current_game = copy.deepcopy(self)
                        current_game.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(self.min_value(current_game, depth, alpha, beta))
                        values.append(np.max(values_temp))
                        values_temp = []
                    else:
                        current_game.move(moves[0], moves[1], moves[2])
                        values.append(self.min_value(current_game, depth, alpha, beta))
                else:
                    current_game.move(moves[0], moves[1], moves[2])
                    values.append(self.min_value(current_game, depth, alpha, beta))
            else:
                current_game.move(moves[0], moves[1], moves[2])
                values.append(self.min_value(current_game, depth, alpha, beta))
        max_ind = int(np.argmax(values))
        b_move = legal_moves[max_ind]

        return b_move

    def min_value(self, current_game, depth, alpha, beta):
        legal_moves = current_game.find_legal_moves(current_game.current_player)
        if len(legal_moves) == 0:  # if the game was over
            return utility(current_game.board, 1)
        if depth == 0:  # if the game wasn't over, but met the depth limitation
            return utility(current_game.board, 0)
        values = []
        values_temp = []
        for moves in legal_moves:
            game_board = copy.deepcopy(current_game)
            if moves[2] == Piece.pawn:
                if moves[1][0] - moves[0][0] == 1:
                    if moves[1][0] == 7:
                        game_board.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        values.append(np.min(values_temp))
                        values_temp = []
                    else:
                        game_board.move(moves[0], moves[1], moves[2])
                        values.append(game_board.max_value(game_board, depth-1, alpha, beta))
                elif moves[1][0] - moves[0][0] == -1:
                    if moves[1][0] == 0:
                        game_board.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(game_board.max_value(game_board, depth-1, alpha, beta))
                        values.append(np.min(values_temp))
                        values_temp = []
                    else:
                        game_board.move(moves[0], moves[1], moves[2])
                        values.append(game_board.max_value(game_board, depth-1, alpha, beta))
                else:
                    game_board.move(moves[0], moves[1], moves[2])
                    values.append(game_board.max_value(game_board, depth-1, alpha, beta))
            else:
                game_board.move(moves[0], moves[1], moves[2])
                values.append(game_board.max_value(game_board, depth-1, alpha, beta))
            mini = np.min(values)
            beta = np.min([mini, beta])
            if alpha >= beta:
                break
        return beta

    def max_value(self, current_game, depth, alpha, beta):
        legal_moves = current_game.find_legal_moves(current_game.current_player)
        if len(legal_moves) == 0:  # if the game was over
            return utility(current_game.board, current_game.current_player)
        if depth == 0:  # if the game wasn't over, but met the depth limitation
            return utility(current_game.board, current_game.current_player)
        values = []
        values_temp = []
        for moves in legal_moves:
            game_board = copy.deepcopy(current_game)
            if moves[2] == Piece.pawn:
                if moves[1][0] - moves[0][0] == 1:
                    if moves[1][0] == 7:
                        game_board.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        values.append(np.max(values_temp))
                        values_temp = []
                    else:
                        game_board.move(moves[0], moves[1], moves[2])
                        values.append(game_board.min_value(game_board, depth-1, alpha, beta))
                else:
                    if moves[1][0] == 0:
                        game_board.move(moves[0], moves[1], moves[2], Piece.rook)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.knight)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.bishop)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        game_board = copy.deepcopy(current_game)
                        game_board.move(moves[0], moves[1], moves[2], Piece.queen)
                        values_temp.append(game_board.min_value(game_board, depth-1, alpha, beta))
                        values.append(np.max(values_temp))
                        values_temp = []
                    else:
                        game_board.move(moves[0], moves[1], moves[2])
                        values.append(game_board.min_value(game_board, depth-1, alpha, beta))
            else:
                game_board.move(moves[0], moves[1], moves[2])
                values.append(game_board.min_value(game_board, depth-1, alpha, beta))
            maxi = np.max(values)
            alpha = np.max([maxi, alpha])
            if alpha >= beta:
                break
        return alpha


    @staticmethod
    def square_name(name):  # convert square name into square id
        i = int(name[1]) - 1
        if name[0] == 'A' or name[0] == 'a':
            j = 0
        elif name[0] == 'B' or name[0] == 'b':
            j = 1
        elif name[0] == 'C' or name[0] == 'c':
            j = 2
        elif name[0] == 'D' or name[0] == 'd':
            j = 3
        elif name[0] == 'E' or name[0] == 'e':
            j = 4
        elif name[0] == 'F' or name[0] == 'f':
            j = 5
        elif name[0] == 'G' or name[0] == 'g':
            j = 6
        elif name[0] == 'H' or name[0] == 'h':
            j = 7
        else:
            print("square_name converts illegal name")
            j = 0
        return [i, j]

def is_check(board, player):  # define if player is being checked(将军)
    count = 0  # the number of enemy pieces that attacks the opposite king, may be 0,1 or 2 in valid states.
    attackers = []  # the location and piece_name of all attackers
    # search for the king
    for i in range(8):
        for j in range(8):
            if board[i][j].piece == Piece.king and board[i][j].piece_color == player:
                # main part
                # check straight line attackers (queen, rook & bishop)
                for direction in range(8):
                    temp_i = i
                    temp_j = j
                    while 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                        # for empty line, continue search
                        dir_x = [-1, 1, 0, 0, -1, 1, 1, -1]
                        dir_y = [0, 0, 1, -1, 1, 1, -1, -1]
                        if board[temp_i][temp_j].piece == Piece.empty or (temp_i == i and temp_j == j):

                            temp_i = temp_i + dir_x[direction]
                            temp_j = temp_j + dir_y[direction]
                            continue
                        # found an attacker piece: for dir=0~3,found rook or queen;for dir=4~7,found bishop or queen
                        elif board[temp_i][temp_j].piece_color != player \
                                and (board[temp_i][temp_j].piece == Piece.queen
                                        or (0 <= direction <= 3 and board[temp_i][temp_j].piece == Piece.rook)
                                        or (4 <= direction <= 7 and board[temp_i][temp_j].piece == Piece.bishop)):
                            count = count + 1
                            attackers.append([[temp_i, temp_j], board[temp_i][temp_j].piece])
                            break
                        # found an non_attacker piece (or friendly piece)
                        else:
                            break
                # check knight attackers
                x_values = [1, 2, 2, 1, -1, -2, -2, -1]
                y_values = [2, 1, -1, -2, -2, -1, 1, 2]
                for direction in range(8):
                    temp_i = i + x_values[direction]
                    temp_j = j + y_values[direction]
                    if 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                        if (board[temp_i][temp_j].piece == Piece.knight
                                and board[temp_i][temp_j].piece_color != player):
                            count = count + 1
                            attackers.append([[temp_i, temp_j], board[temp_i][temp_j].piece])
                # check pawn attackers
                if player == Color.white:
                    temp_i = i + 1
                else:
                    temp_i = i - 1
                temp_j = j + 1  # check right
                if 1 <= temp_i <= 6 and 0 <= temp_j <= 7 and board[temp_i][temp_j].piece == Piece.pawn \
                        and board[temp_i][temp_j].piece_color != player:
                    count = count + 1
                    attackers.append([[temp_i, temp_j], board[temp_i][temp_j].piece])
                temp_j = j - 1  # check left
                if 1 <= temp_i <= 6 and 0 <= temp_j <= 7 and board[temp_i][temp_j].piece == Piece.pawn \
                        and board[temp_i][temp_j].piece_color != player:
                    count = count + 1
                    attackers.append([[temp_i, temp_j], board[temp_i][temp_j].piece])

                # check king attacker (used to judge illegal moves)
                x_values = [1, 1, 0, -1, -1, -1, 0, 1]
                y_values = [0, 1, 1, 1, 0, -1, -1, -1]
                for direction in range(8):
                    temp_i = i + x_values[direction]
                    temp_j = j + y_values[direction]
                    if 0 <= temp_i <= 7 and 0 <= temp_j <= 7:
                        if (board[temp_i][temp_j].piece == Piece.king
                                and board[temp_i][temp_j].piece_color != player):
                            count = count + 1
                            attackers.append([[temp_i, temp_j], board[temp_i][temp_j].piece])
    return count, attackers

def check_legal_move(board, src_square_id, dst_square_id, SpecialMovePermissionList):  # check if move violates the rules
    # check square id overflow
    if 0 <= src_square_id[0] <= 7 and 0 <= src_square_id[1] <= 7 \
            and 0 <= dst_square_id[0] <= 7 and 0 <= dst_square_id[1] <= 7:
        pass
    else:
        return False
    player = board[src_square_id[0]][src_square_id[1]].piece_color
    piece = board[src_square_id[0]][src_square_id[1]].piece
    dst_color = board[dst_square_id[0]][dst_square_id[1]].piece_color
    # check empty source square
    if player == Color.none:
        return False
    # check friendly capture
    if player == dst_color:
        return False
    # check same-square move
    if src_square_id == dst_square_id:
        return False

    # 1.check moving rule violence
    if piece == Piece.pawn:
        # just move
        # move 1 square
        if src_square_id[1] == dst_square_id[1] and dst_square_id[0] == src_square_id[0] + player.value \
                and dst_color == Color.none:
            pass
        # first time, move 2 square -- white
        elif src_square_id[1] == dst_square_id[1] and src_square_id[0] == 1 and dst_square_id[0] == 3 \
                and player == Color.white and dst_color == Color.none:
            pass
        # first time, move 2 square -- black
        elif src_square_id[1] == dst_square_id[1] and src_square_id[0] == 6 and dst_square_id[0] == 4 \
                and player == Color.black and dst_color == Color.none:
            pass
        # capture enemy pieces
        elif abs(src_square_id[1] - dst_square_id[1]) == 1 and dst_square_id[0] == src_square_id[0] + player.value \
                and dst_color != Color.none and dst_color != player:
            pass
        # passer-by captures judgement should be added here
        elif [src_square_id, dst_square_id] in SpecialMovePermissionList.white_passerby_square or \
                [src_square_id, dst_square_id] in SpecialMovePermissionList.black_passerby_square:
            pass
        else:
            return False

    elif piece == Piece.knight:
        if ((abs(dst_square_id[0] - src_square_id[0]) == 2 and abs(dst_square_id[1] - src_square_id[1]) == 1)
            or (abs(dst_square_id[0] - src_square_id[0]) == 1 and abs(dst_square_id[1] - src_square_id[1]) == 2)) \
                and dst_color != player:
            pass
        else:
            return False

    elif piece == Piece.bishop:
        # check dialog satisfaction
        if abs(dst_square_id[0] - src_square_id[0]) != abs(dst_square_id[1] - src_square_id[1]):
            return False
        # check block of other pieces
        dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))  # direction
        dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))  # of checking
        temp_i = src_square_id[0] + dir_i
        temp_j = src_square_id[1] + dir_j
        while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
            if board[temp_i][temp_j].piece == Piece.empty:
                temp_i = temp_i + dir_i
                temp_j = temp_j + dir_j
                continue
            else:
                return False  # blocked by other pieces.

    elif piece == Piece.rook:
        # check line satisfaction
        if src_square_id[0] != dst_square_id[0] and src_square_id[1] != dst_square_id[1]:
            return False
        # check block of other pieces
        if src_square_id[0] == dst_square_id[0]:
            dir_i = 0
        else:
            dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))
        if src_square_id[1] == dst_square_id[1]:
            dir_j = 0
        else:
            dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))
        temp_i = src_square_id[0] + dir_i
        temp_j = src_square_id[1] + dir_j
        while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
            if board[temp_i][temp_j].piece == Piece.empty:
                temp_i = temp_i + dir_i
                temp_j = temp_j + dir_j
                continue
            else:
                return False  # blocked by other pieces.

    elif piece == Piece.queen:
        # check dialog or line satisfaction
        if (abs(dst_square_id[0] - src_square_id[0]) != abs(dst_square_id[1] - src_square_id[1])) \
                and (src_square_id[0] != dst_square_id[0] and src_square_id[1] != dst_square_id[1]):
            return False
        # check block of other pieces
        if src_square_id[0] == dst_square_id[0]:
            dir_i = 0
        else:
            dir_i = int((dst_square_id[0] - src_square_id[0]) / abs(dst_square_id[0] - src_square_id[0]))
        if src_square_id[1] == dst_square_id[1]:
            dir_j = 0
        else:
            dir_j = int((dst_square_id[1] - src_square_id[1]) / abs(dst_square_id[1] - src_square_id[1]))
        temp_i = src_square_id[0] + dir_i
        temp_j = src_square_id[1] + dir_j
        while temp_i != dst_square_id[0] and temp_j != dst_square_id[1]:
            if board[temp_i][temp_j].piece == Piece.empty:
                temp_i = temp_i + dir_i
                temp_j = temp_j + dir_j
                continue
            else:
                return False  # blocked by other pieces.
    elif piece == Piece.king:
        # castling check
        if player == Color.white:
            # white attempts to 0-0
            if src_square_id == [0, 4] and dst_square_id == [0, 6] and SpecialMovePermissionList.white0_0:
                # castling is blocked by other pieces
                if board[0][5].piece != piece.empty or board[0][6].piece != piece.empty:
                    return False
                # put extra kings on the board to test if king is being attacked before/while in/after castling.
                board[0][5].piece = Piece.king
                board[0][6].piece = Piece.king
                board[0][5].piece_color = Color.white
                board[0][6].piece_color = Color.white
                count, attackers = is_check(board, player)
                if count != 0:
                    return False
                # not being checked, nor banned by SpecialMovePermissionList
                return True
            # white attempts to 0-0-0
            elif src_square_id == [0, 4] and dst_square_id == [0, 2] and SpecialMovePermissionList.white0_0_0:
                # castling is blocked by other pieces
                if board[0][3].piece != piece.empty or board[0][2].piece != piece.empty:
                    return False
                # put extra kings on the board to test if king is being attacked before/while in/after castling.
                board[0][3].piece = Piece.king
                board[0][2].piece = Piece.king
                board[0][3].piece_color = Color.white
                board[0][2].piece_color = Color.white
                count, attackers = is_check(board, player)
                if count != 0:
                    return False
                # not being checked, nor banned by SpecialMovePermissionList
                return True
        elif player == Color.black:
            # black attempts to 0-0
            if src_square_id == [7, 4] and dst_square_id == [7, 6] and SpecialMovePermissionList.black0_0:
                # castling is blocked by other pieces
                if board[7][5].piece != piece.empty or board[7][6].piece != piece.empty:
                    return False
                # put extra kings on the board to test if king is being attacked before/while in/after castling.
                board[7][5].piece = Piece.king
                board[7][6].piece = Piece.king
                board[7][5].piece_color = Color.black
                board[7][6].piece_color = Color.black
                count, attackers = is_check(board, player)
                if count != 0:
                    return False
                # not being checked, nor banned by SpecialMovePermissionList
                return True
            elif src_square_id == [7, 4] and dst_square_id == [7, 2] and SpecialMovePermissionList.black0_0_0:
                # castling is blocked by other pieces
                if board[7][3].piece != piece.empty or board[7][2].piece != piece.empty:
                    return False
                # put extra kings on the board to test if king is being attacked before/while in/after castling.
                board[7][3].piece = Piece.king
                board[7][2].piece = Piece.king
                board[7][3].piece_color = Color.black
                board[7][2].piece_color = Color.black
                count, attackers = is_check(board, player)
                if count != 0:
                    return False
                # not being checked, nor banned by SpecialMovePermissionList
                return True

        # check distance satisfaction
        if abs(dst_square_id[0] - src_square_id[0]) > 1 or abs(dst_square_id[1] - src_square_id[1]) > 1:
            return False

    # 2. check king-being-attacked violence
    board[dst_square_id[0]][dst_square_id[1]].piece = \
        board[src_square_id[0]][src_square_id[1]].piece
    board[dst_square_id[0]][dst_square_id[1]].piece_color = \
        board[src_square_id[0]][src_square_id[1]].piece_color
    board[src_square_id[0]][src_square_id[1]].piece = Piece.empty
    board[src_square_id[0]][src_square_id[1]].piece_color = Color.none
    count, attackers = is_check(board, player)
    if count != 0:
        return False

    # after all rule violence check
    return True

def location_value(i, j, piece):
    value = 1
    pawn_value = [[25,  25,  25,  25,  25,  25,  25,  25 ],
                    [25,  25,  25,  25,  25,  25,  25,  25 ],
                    [5,   5,   10,  15,  15,  10,  5,   5  ],
                    [2.5, 2.5, 5,   12.5,12.5,5 ,  2.5, 2.5],
                    [0,   0,   0,   10,  10,  0,   0,   0  ],
                    [2.5, -2.5,-5,  0,   0,   -5,  -2.5,2.5],
                    [2.5, 5,   5,   -10, -10, 5,   5,   2.5],
                    [0,   0,   0,   0,   0,   0,   0,   0 ]]
    rook_value = [[0, 0, 0, 0, 0, 0, 0, 0],
                    [2.5, 5, 5, 5, 5, 5, 5, 2.5],
                    [-2.5, 0, 0, 0, 0, 0, 0, -2.5],
                    [-2.5, 0, 0, 0, 0, 0, 0, -2.5],
                    [-2.5, 0, 0, 0, 0, 0, 0, -2.5],
                    [-2.5, 0, 0, 0, 0, 0, 0, -2.5],
                    [-2.5, 0, 0, 0, 0, 0, 0, -2.5],
                    [0, 0, 0, 2.5, 2.5, 0, 0, 0 ]]
    knight_value = [[-25, -20, -15, -15, 15, -15, -20, -25],
                    [-20, -10, 0, 0, 0, 0, -10, -20],
                    [-15, 0, 5, 7.5,7.5, 5, 0, -15],
                    [-15, 2.5, 7.5, 10, 10, 7.5, 2.5, -15],
                    [-15, 0, 7.5, 10,10, 7.5, 0, -15],
                    [-15, 2.5, 5, 7.5, 7.5, 5, 2.5, -15],
                    [-20, -10, 0, 2.5, 2.5, 0, -10, -20],
                    [-25, -20, -15, -15, 15, -15, -20, -25]]
    bishop_value = [[-10, -5, -5, -5, 5, -5, -5, -10],
                    [-5, 0, 0, 0, 0, 0, 0, -5],
                    [-5, 0, 2.5, 5,5, 2.5, 0, -5],
                    [-5, 2.5, 2.5, 5, 5, 2.5, 2.5, -5],
                    [-5, 0, 5, 5, 5, 5, 0, -5],
                    [-5, 5, 5, 5, 5, 5, 5, -5],
                    [-5, 2.5, 0, 2.5, 2.5, 0, 2.5, -5],
                    [-10, -5, -5, -5, -5, -5, -5, -10]]
    queen_value = [[-10, -5, -5, -2.5, -2.5, -5, -5, -10],
                    [-5, 0, 0, 0, 0, 0, 0, -5],
                    [-5, 0, 2.5, 2.5, 2.5, 2.5, 0, -5],
                    [-2.5, 0, 2.5, 2.5, 2.5, 2.5, 0, -2.5],
                    [0, 0, 2.5, 2.5, 2.5, 2.5, 0, -2.5],
                    [-5, 2.5, 2.5, 2.5, 2.5, 2.5, 0, -5],
                    [-5, 0, 2.5, 0, 0, 0, 0, -5],
                    [-10, -5, -5, -2.5, -2.5, -5, -5, -10]]
    king_value = [[-15, -20, -20, -25, -25, -20, -20, -15],
                    [-15, -20, -20, -25, -25, -20, -20, -15],
                    [-15, -20, -20, -25, -25, -20, -20, -15],
                    [-15, -20, -20, -25, -25, -20, -20, -15],
                    [-10, -15, -15, -20, -20, -15, -15, -10],
                    [-5, -10, -10, -10, -10, -10, -10, -5],
                    [10, 10, 0, 0, 0, 0, 10, 10],
                    [10, 15, 5, 0, 0, 5, 15, 10]]
    if piece == Piece.pawn:
        value = pawn_value[i][j]
    elif piece == Piece.rook:
        value = rook_value[i][j]
    elif piece == Piece.knight:
        value = knight_value[i][j]
    elif piece == Piece.bishop:
        value = bishop_value[i][j]
    elif piece == Piece.queen:
        value = queen_value[i][j]
    elif piece == Piece.king:
        value = king_value[i][j]
    else:
        value = 1;
    return value

def utility(board, white_player):
    if white_player == 0:
        pos_color = 1
    else:
        pos_color = -1
    piece_score = 0
    loc_score = 0
    piece_power = 0.5
    loc_power = 0.5
    for i in range(8):
        for j in range(8):
            if board[i][j].piece_color == Color.white:
                if board[i][j].piece == Piece.pawn:
                    piece_score = piece_score + 10 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.pawn) * pos_color
                elif board[i][j].piece == Piece.rook:
                    piece_score = piece_score + 50 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.rook) * pos_color
                elif board[i][j].piece == Piece.knight:
                    piece_score = piece_score + 30 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.knight) * pos_color
                elif board[i][j].piece == Piece.bishop:
                    piece_score = piece_score + 30 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.bishop) * pos_color
                elif board[i][j].piece == Piece.queen:
                    piece_score = piece_score + 90 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.queen) * pos_color
                elif board[i][j].piece == Piece.king:
                    piece_score = piece_score + 900 * pos_color
                    loc_score = loc_score + location_value(i, j, Piece.king) * pos_color
            elif board[i][j].piece_color == Color.black:
                if board[i][j].piece == Piece.pawn:
                    piece_score = piece_score - 10 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.pawn) * pos_color
                elif board[i][j].piece == Piece.rook:
                    piece_score = piece_score - 50 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.rook) * pos_color
                elif board[i][j].piece == Piece.knight:
                    piece_score = piece_score - 30 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.knight) * pos_color
                elif board[i][j].piece == Piece.bishop:
                    piece_score = piece_score - 30 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.bishop) * pos_color
                elif board[i][j].piece == Piece.queen:
                    piece_score = piece_score - 90 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.queen) * pos_color
                elif board[i][j].piece == Piece.king:
                    piece_score = piece_score - 900 * pos_color
                    loc_score = loc_score - location_value(7-i, j, Piece.king) * pos_color

    score = piece_power * piece_score + loc_power * loc_score

    return score

def get_promote_piece(dst_square_id):
    return Piece.queen

def move_board(board, src_square_id, dst_square_id, src_piece, SpecialMovePermissionList, promote_piece=Piece.empty):
    promote_flag = 0  # if this move is a promote, this flag is 1
    piece_color = board[src_square_id[0]][src_square_id[1]].piece_color
    piece = board[src_square_id[0]][src_square_id[1]].piece
    if board[src_square_id[0]][src_square_id[1]].piece == Piece.empty:
        return 0, 0  # invalid move for empty source square
    if not check_legal_move(src_square_id, dst_square_id, SpecialMovePermissionList):
        return -1, 0  # invalid move for rule violence
    if board[dst_square_id[0]][dst_square_id[1]].piece != Piece.empty:
        capture_flag = 2  # capture
    else:
        capture_flag = 1  # no capture
    if (dst_square_id[0] == 7 or dst_square_id[0] == 0) \
            and board[src_square_id[0]][src_square_id[1]].piece == Piece.pawn:
        promote_flag = 1
        if promote_piece == Piece.empty:  # unspecified promote piece
            board[dst_square_id[0]][dst_square_id[1]].piece = get_promote_piece(dst_square_id)
        else:  # specified promote piece
            board[dst_square_id[0]][dst_square_id[1]].piece = promote_piece
    # move piece from src square to dst square
    else:
        board[dst_square_id[0]][dst_square_id[1]].piece = board[src_square_id[0]][src_square_id[1]].piece
    board[dst_square_id[0]][dst_square_id[1]].piece_color = \
        board[src_square_id[0]][src_square_id[1]].piece_color
    board[src_square_id[0]][src_square_id[1]].clear()

    # if castling, move rook by king's the other side
    # white 0-0
    if src_square_id == [0, 4] and dst_square_id == [0, 6] and src_piece == Piece.king:
        board[0][7].clear()
        board[0][5].piece = Piece.rook
        board[0][5].piece_color = Color.white
    # white 0-0-0
    elif src_square_id == [0, 4] and dst_square_id == [0, 2] and src_piece == Piece.king:
        board[0][0].clear()
        board[0][3].piece = Piece.rook
        board[0][3].piece_color = Color.white
    # black 0-0
    elif src_square_id == [7, 4] and dst_square_id == [7, 6] and src_piece == Piece.king:
        board[7][7].clear()
        board[7][5].piece = Piece.rook
        board[7][5].piece_color = Color.black
    # black 0-0-0
    elif src_square_id == [7, 4] and dst_square_id == [7, 2] and src_piece == Piece.king:
        board[7][0].clear()
        board[7][3].piece = Piece.rook
        board[7][3].piece_color = Color.black

    # update SpecialMovePermissionList
    # check passer-by:
    if piece_color == Color.white:
        # if taking passer-by, clear opposite pawn square
        if [src_square_id, dst_square_id] in SpecialMovePermissionList.white_passerby_square:
            board[dst_square_id[0] - 1][dst_square_id[1]].piece = Piece.empty
            board[dst_square_id[0] - 1][dst_square_id[1]].piece_color = Color.none
        # clear opposite passerby square
        SpecialMovePermissionList.white_passerby_square.clear()
        if piece == Piece.pawn and src_square_id[0] == 1 and dst_square_id[0] == 3:
            # check left side
            if src_square_id[1] != 0:
                if board[3][src_square_id[1] - 1].piece == Piece.pawn and \
                        board[3][src_square_id[1] - 1].piece_color == Color.black:
                    SpecialMovePermissionList.black_passerby_square.append([[3, src_square_id[1] - 1],
                                                                                    [2, src_square_id]])
            # check right side
            if src_square_id[1] != 7:
                if board[3][src_square_id[1] + 1].piece == Piece.pawn and \
                        board[3][src_square_id[1] + 1].piece_color == Color.black:
                    SpecialMovePermissionList.black_passerby_square.append([[3, src_square_id[1] + 1],
                                                                                    [2, src_square_id]])
    if piece_color == Color.black:
        # if taking passer-by, clear opposite pawn square
        if [src_square_id, dst_square_id] in SpecialMovePermissionList.black_passerby_square:
            board[dst_square_id[0] + 1][dst_square_id[1]].piece = Piece.empty
            board[dst_square_id[0] + 1][dst_square_id[1]].piece_color = Color.none
        # clear opposite passerby square
        SpecialMovePermissionList.black_passerby_square.clear()
        if piece == Piece.pawn and src_square_id[0] == 6 and dst_square_id[0] == 4:
            # check left side
            if src_square_id[1] != 0:
                if board[4][src_square_id[1] - 1].piece == Piece.pawn and \
                        board[4][src_square_id[1] - 1].piece_color == Color.white:
                    SpecialMovePermissionList.white_passerby_square.append([[4, src_square_id[1] - 1],
                                                                                    [5, src_square_id[1]]])
            # check right side
            if src_square_id[1] != 7:
                if board[4][src_square_id[1] + 1].piece == Piece.pawn and \
                        board[4][src_square_id[1] + 1].piece_color == Color.white:
                    SpecialMovePermissionList.white_passerby_square.append([[4, src_square_id[1] + 1],
                                                                                    [5, src_square_id[1]]])

    # check castle:
    # firstly, check if rook and king is still in their original square
    # check white 0-0:
    if SpecialMovePermissionList.white0_0:
        # piece in square h1 is not white rook: deny white 0-0
        if board[0][7].piece != Piece.rook or board[0][7].piece_color != Color.white:
            SpecialMovePermissionList.white0_0 = False
        # piece in square e1 is not white king: deny white castling
        if board[0][4].piece != Piece.king or board[0][4].piece_color != Color.white:
            SpecialMovePermissionList.white0_0_0 = False
            SpecialMovePermissionList.white0_0 = False
    # check white 0-0-0:
    if SpecialMovePermissionList.white0_0_0:
        # piece in square a1 is not white rook: deny white 0-0_0
        if board[0][0].piece != Piece.rook or board[0][0].piece_color != Color.white:
            SpecialMovePermissionList.white0_0_0 = False
        # piece in square e1 is not white king: deny white castling
        if board[0][4].piece != Piece.king or board[0][4].piece_color != Color.white:
            SpecialMovePermissionList.white0_0_0 = False
            SpecialMovePermissionList.white0_0 = False

    # check black 0-0:
    if SpecialMovePermissionList.black0_0:
        # piece in square h8 is not black rook: deny black 0-0
        if board[7][7].piece != Piece.rook or board[7][7].piece_color != Color.black:
            SpecialMovePermissionList.black0_0 = False
        # piece in square e8 is not black king: deny black castling
        if board[7][4].piece != Piece.king or board[7][4].piece_color != Color.black:
            SpecialMovePermissionList.black0_0_0 = False
            SpecialMovePermissionList.black0_0 = False

    # check black 0-0-0:
    if SpecialMovePermissionList.black0_0_0:
        # piece in square a8 is not black rook: deny black 0-0-0
        if board[7][0].piece != Piece.rook or board[7][0].piece_color != Color.black:
            SpecialMovePermissionList.black0_0_0 = False
        # piece in square e8 is not black king: deny black castling
        if board[7][4].piece != Piece.king or board[7][4].piece_color != Color.black:
            SpecialMovePermissionList.black0_0_0 = False
            SpecialMovePermissionList.black0_0 = False

    # secondly, check the current move ( e.g: after king moves, deny both side castling)
    if piece == Piece.king:
        if piece_color == Color.white:
            SpecialMovePermissionList.white0_0 = False
            SpecialMovePermissionList.white0_0_0 = False
        elif piece_color == Color.black:
            SpecialMovePermissionList.black0_0 = False
            SpecialMovePermissionList.black0_0_0 = False

    elif piece == Piece.rook:
        if piece_color == Color.white:
            if src_square_id == [0, 0]:  # a1 rook moves, deny white 0-0-0
                SpecialMovePermissionList.white0_0_0 = False
            elif src_square_id == [0, 7]:  # h1 rook moves, deny white 0-0
                SpecialMovePermissionList.white0_0 = False
        elif piece_color == Color.black:
            if src_square_id == [7, 0]:  # a8 rook moves, deny black 0-0-0
                SpecialMovePermissionList.black0_0_0 = False
            elif src_square_id == [7, 7]:  # h8 rook moves, deny black 0-0
                SpecialMovePermissionList.black0_0 = False


    return capture_flag, promote_flag

def find_pieces(piece, dst_square_id, legal_moves):  # find all target pieces that can reach dst_square
    inspection_list = []
    for legal_move in legal_moves:
        if legal_move[2] == piece and legal_move[1] == dst_square_id:
            inspection_list.append(legal_move[0])
    return inspection_list


def is_letter(ch):
    if 'a' <= ch <= 'z':
        return 1
    elif 'A' <= ch <= 'z':
        return 2
    else:
        return 0


def is_num(ch):
    return '0' <= ch <= '9'

